public class LinkedList<E> {

    private class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {

            this.e = e;
            this.next = next;
        }

        public Node() {
            this(null, null);
        }

        public Node(E e) {
            this(e, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node head;
    private int size;



    public LinkedList() {
        head = null;//指向链表中的第一个节点，默认为空

        size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    //在链表头增加元素,如果不理解可以想象将666这个元素放入0 1 2 这个链表里
    public void addFirst(E e) {
        //先new出来一个节点，
        Node node = new Node(e);
        node.next = head;//将新的元素的next指向目前的head
        //然后把新的head赋值给这个new出来的新node
        head = node;
        //以上三句可以简化为 head=new Node(e,head)
        size++;
    }

    //在链表中间增加元素
    public void add(int index, E e) {
        if (index < 0 || index > size) {//注意这里index是可以取到size的，代表从链表末尾添加一个元素
            throw new IllegalArgumentException("add failed,illegal index");
        }

        //找到prev，为index-1位置的，prev默认为0。关键是找到要插入节点的前一个节点。（考虑链表头部是没有prev节点的，在此需要特殊处理一下）
        if (index == 0) {
            addFirst(e);
        } else {
            Node prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            Node node = new Node(e);
            //找到node之前的元素prev,把prev.next指向666
            node.next = prev.next;
            prev.next = node;

            //prev.next=new Node(e,prev.next);这句话可以代替以上三句

            size++;
        }
        //
        //
    }

    public void addLast(E e) {
        add(size, e);
    }

}
